package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)103. 二叉树的锯齿形层次遍历
 * @author: jie.deng
 * @time: 2019年3月14日 上午9:12:48
 */
public class MySolution0314 {
	
	/**
	 * 103. 二叉树的锯齿形层次遍历
	 * 
	 * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
	 * 
	 * 例如：
	 * 给定二叉树 [3,9,20,null,null,15,7],
	 * 
	 *     3
	 *    / \
	 *   9  20
	 *     /  \
	 *    15   7
	 * 返回锯齿形层次遍历如下：
	 *	 
	 * [
	 *   [3],
	 *   [20,9],
	 *   [15,7]
	 * ]
	 * @param root
	 * @return
	 */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (root == null) {
			return list;
		}
		Queue<BinaryNodeAndNum> queue = new LinkedList<BinaryNodeAndNum>();
		queue.offer(new BinaryNodeAndNum(root, 1)); // 根结点的level = 1
		while (!queue.isEmpty()) {
			BinaryNodeAndNum poll = queue.poll();
			List<Integer> levelList = null;
			int curLevel = poll.num;
			if (list.size() >= curLevel) {
				levelList = list.get(curLevel - 1);
			} else {
				levelList = new ArrayList<Integer>();
				list.add(levelList);
			}
			TreeNode cur = poll.node;
			if (curLevel % 2 == 0) {
				levelList.add(0, cur.val);
			} else {
				levelList.add(cur.val);
			}
			if (cur.left != null) {
				queue.offer(new BinaryNodeAndNum(cur.left, curLevel + 1));
			}
			if (cur.right != null) {
				queue.offer(new BinaryNodeAndNum(cur.right, curLevel + 1));
			}
		}
		return list;
    }
    
	class BinaryNodeAndNum {
		public TreeNode node;
		public int num;

		public BinaryNodeAndNum(TreeNode node, int num) {
			super();
			this.node = node;
			this.num = num;
		}
	}
}
